The present invention relates to an electronic transaction system which electronically effects commercial transactions by computer documents instead of conventional documents.
In the past, contracts have been authenticated or validated by signatures or seals. Where data is transmitted through a communication like electronic transaction between two parties having interests to each other, even if the signature and seal data are converted to digital signals for transmission, they may be easily copied and hence they cannot be used for authenticity. Accordingly, the authenticity of the message by digital signature which corresponds to the normal signature and seal is required. In order for the message authenticity to be effective as a formal transaction in place of the signature or seal, the following four conditions should be met.
(a) Only the transmitter can prepare a signed message such as a contract. It cannot be forged by a third person.
(b) The receiver cannot alter the signed message.
(c) The transmitter cannot later deny the fact of transmission which includes the indication that he/she has approved of the content of the message.
(d) The receiver cannot later deny the fact of reception which includes the indication that he/she has approved the content of the message.
(e) In the signing contract process, troubles such as data mismatching can be adequately arbitrated.
The following methods have been proposed to achieve the digital signature.
(1) Digital signature which uses conventional cryptograph
(2) Digital signature which uses public key cryptograph
(3) Digital signature by hybrid system
Characteristics and problems relating to those three methods are described below.
(1) Digital signature which uses conventional cryptograph
Many digital signature methods which use the DES (data encryption standard) system cryptograph have been proposed but notarization is required or the receiver can alter the signed message because the transmitting station and the receiving station have a common authenticity key. Accordingly, no practical signature system has been known.
(2) Digital signature which uses public key cryptograph
The digital signature can be relatively easily attained by using the public key cryptograph system represented by an RSA (Rivest-Shamir-Adleman) algorithm.
FIG. 1 shows a chart of a prior art digital signature by the public key cryptograph.
In a step 101, a message M from a sender A is inputted.
In a step 102, a decoded message D (M, SK.sub.A) is produced by decoding (deciphering) the message M by a secret key SK.sub.A of the sender A.
In a step 103, the decoded message D (M, SK.sub.A) is further encoded (enciphered) by a public key PK.sub.B of a receiver B to produce a cryptograph message L=E (D (M, SK.sub.A), PK.sub.B), which is sent to the receiver B.
In a step 104, the data L received by the receiver B is decoded by the secret key SK.sub.B of the receiver B to produce D (M, SK.sub.A).
In a step 105, the decoded message D (M, SK.sub.A) is encoded by the public key PK.sub.A of the sender A to produce the original message M.
In a step 106, the message M is supplied to the receiver B as output data.
In the present flow chart, the cryptograph message M cannot be decoded in the step 104 unless the secret key SK.sub.B is known. Only the receiver B knows SK.sub.B. In the step 102, only the sender A who knows the secret key SK.sub.A can produce D (M, SK.sub.A). Accordingly, it is assumed that it is A that has sent the message M and it is B that has received the message.
When the message M is not a conventional sentence but random data, it is difficult to determine whether M is proper or not. As an approach thereto, an identifier of the sender, an identifier of the receiver, a serial number of the message and a date may be sent together with the message. In this case, an unauthorized act such as copying the signed message for repetitive transmission is prevented.
However, in the RSA system, the encoding and decoding time is long because of the complexity of the operations and a time-consuming problem will arise when the message is long.
(3) Digital signature by hybrid system
This system utilizes the advantages of the DES cryptograph system and the RSA cryptograph system in a well-mixed manner.
In this system, the conventional (ordinary) message is sent by the DES cryptograph communication and the transmission of the key and the authenticity utilize the RSA system. The message to be authenticated (validated) is first compression-decoded by the DES system to determine the Hash Total. FIG. 2A shows a process therefor. In FIG. 2A, the following steps are carried out.
Step 1:
First 64 bits of an input message I are defined as I.sub.1. The I.sub.1 portion is encoded by an encoder 21 by using a cryptograph key K. The encoded result is defined as O.sub.1. EQU E.sub.k (I.sub.1).fwdarw.O.sub.1
The 64 bits of an input message subsequent to the first 64(i-1) bits are defined as I.sub.i.
Step 2:
Next 64 bits of the input message which follow portion I.sub.i are defined as I.sub.i+1. An exclusive OR circuit 22 exclusively ORs I.sub.i+1 and O.sub.i and an output thereof is encoded by the encoder 21 by using the key K. EQU E.sub.k (I.sub.i+1 +O.sub.i).fwdarw.O.sub.i+1
Step 3:
If i&lt;n-1, i is incremented by one and the process returns to the step 2. If not i&lt;n-1, O.sub.i+1 =O.sub.n is outputted and the process is terminated. The RSA system digital signature is effected only for the data having the finally produced cryptograph block (Hash total) O.sub.n and data information added thereto.
In this system, even the digital signature to a long message can be processed in a short time.
However, the above systems do not meet the above-mentioned condition (c) of the digital signature, that is, "the sender cannot later deny the fact of transmission". In the system which uses either the conventional cryptograph or the public key cryptograph, if the sender falsely insists that the secret key has been stolen and someone has prepared data without authorization, it is difficult to determine whether this allegation is true or not.
If the secret key has been actually stolen, it turns out that all messages signed before are uncreditable. Accordingly, in the digital signature, there is a severe requirement that the secret key must be absolutely protected.
As described above, the condition (c) is not met so long as the signatures are made by only the two persons, the sender and the receiver.
It has been proposed to meet the condition (c) by communicating through a reliable authentication (notary) organization. FIG. 3 illustrates a principle thereof.
In FIG. 3, a sender 34 sends data consisting of a message and signature to an authentication organization 31. The authentication organization 31 adds date information to the received data 35 to prepare data 32, which is sent to a receiver 33 and is also recorded in a log 37. The sender 34 cannot later deny his message because the record is logged in the log 37 of the authentication organization 31. In this case, the sender may insist that the secret key has been stolen and someone has forged the message. Such insistence can be prevented by sending the same data 36 as the data 32 back to the sender 34 for confirmation.
Other problems relate to who the authentication organization should be and (ii) a large volume of message to be recorded.
The problem (i) is that the authentication organization should be operated at every time when the message is exchanged between the sender and the receiver. In a large network, the overhead for the authentication organization becomes very large. The problem (ii) is overcome by introducing Hash total.
As a modification of (3), a method for determining a Hash total by data compression encoding by DES in the hybrid digital signature is explained with reference to FIG. 4.
In FIG. 4, the following steps are carried out. Step 201:
An input message M is divided into n 56-bit blocks M1, M2, . . . Mn. Here the authentication organization usually does not intervene except for trouble time. EQU M=M1, M2, . . . Mn
Step 202:
A parity bit is added to every seven bits of Mi (i=1, 2, . . . n) to produce Ki (i=1, 2, . . . n).
Step 203:
The following step is repeated for j=1, 2, . . . n.
I(j-1) is encoded by using Kj as a cryptograph key, and the encoded result and I(j-1) are exclusively ORed to produce I(j). EQU I(j).rarw.I(j-1).sym.EKj (I(j-1))
where I(o) is an initial value.
Step 204: EQU H(M)=I(n)
Digital signature by the RSA system is applied to the resulting cryptograph block compression encoded message H(M).
Furthermore, this method does not meet the above-mentioned condition (e). If the sender sends a digital signature E (H(M), S.sub.K) without the agreement of the receiver, the signature is not easily teared away because it is easily replicated.
Referring to FIG. 2B, a method of digital signature by the hybrid system is explained.
A sender 301 calculates a short character string H(M) from a message M 302 by data compression encoding, produces a digital signature E (H(M), S.sub.k) 306 by an encoder 305 by using a secret key S.sub.k 304 and sends it to a receiver 307. In order for the receiver 307 to recognize that the message 302 and the digital signature 306 are true and valid, the receiver 307 decodes the digital signature E (H(M), S.sub.k) 306 by a decoder 309 to produce the original character string H(M)' 310, and calculates a character string H(M)" 311 from the message 302 in the same manner as the sender 301 did. Both are compared by a comparator 312 and if they are equal, the message 302 is true and valid so long as the receiver believes that the sender 301 is a sole owner of the secret key S.sub.k 304.
In this method, the digital signature to a long message can be processed in a short time, but this method does not meet the condition (d) (the receiver cannot later deny the fact of reception). If the receiver later denies the fact of reception, the sender has no evidence to refute it.